import java.util.HashMap;
import java.util.Map;

public class SubarraySumsDivisibleByK {
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer, Integer> hash = new HashMap<>();

        // 如果整个数组之和都能整除 k, 需要加上这个特殊情况
        hash.put(0 % k, 1);

        int ret = 0;
        int dp = 0;

        for(int x : nums) {
            dp += x;
            int t = (dp % k + k) % k; // 取余
            ret += hash.getOrDefault(t, 0);
            hash.put(t, hash.getOrDefault(t, 0) + 1); // 注意存的是余数
        }

        return ret;
    }
}
